package com.xiaoyu.awakening.common.core.alms.backtrace;


import java.util.Collections;
import java.util.List;
import java.util.function.Function;

/**
 * 回溯算法代码模版
 *
 * @author wangxiaoyu
 * @date 2024/7/29 14:27
 * @since v1.0
 */
public abstract class AbstractBacktrace<T> {
    /**
     * 回溯算法框架
     *
     * @param currentStates 当前状态
     * @param choices       选择列表
     * @param dealSolution  解处理
     * @author wangxiaoyu
     * @date 2024/7/29 14:43
     * @since v1.0
     */
    public void backtrace(List<T> currentStates, List<T> choices, Function<List<T>, ?> dealSolution) {
        // 检查是否为解
        if (isSolution(currentStates)) {
            dealSolution.apply(currentStates);
        }
        // 遍历选择列表
        for (T choice : choices) {
            // 剪支：检查选择合法性
            if (isValid(currentStates, choice)) {
                // 尝试
                doChoice(currentStates, choice);
                // 下一轮选择
                backtrace(currentStates, Collections.singletonList(choice), dealSolution);
                // 回退
                undoChoice(currentStates, choice);
            }
        }
    }

    /**
     * 撤销选择
     *
     * @param currentStates 当前状态
     * @param choice        当前选择
     * @author wangxiaoyu
     * @date 2024/7/29 14:37
     * @since v1.0
     */
    protected abstract void undoChoice(List<T> currentStates, T choice);

    /**
     * 做出选择
     *
     * @param currentStates 当前状态
     * @param choice        当前选择
     * @author wangxiaoyu
     * @date 2024/7/29 14:38
     * @since v1.0
     */
    protected abstract void doChoice(List<T> currentStates, T choice);

    /**
     * 选择检查
     *
     * @param currentStates 当前状态
     * @param choice        当前选择
     * @return boolean 检查结果
     * @author wangxiaoyu
     * @date 2024/7/29 14:39
     * @since v1.0
     */
    protected abstract boolean isValid(List<T> currentStates, T choice);

    /**
     * 是否为解
     *
     * @param currentStates 当前状态
     * @return boolean 结果
     * @author wangxiaoyu
     * @date 2024/7/29 14:41
     * @since v1.0
     */
    protected abstract boolean isSolution(List<T> currentStates);

}
